package imooc_math;
//路径压缩
//并查集的操作，时间复杂度是近乎O（1）
public class UF4 {
	public int[] parent;
	public int count;
	public int[] rank;//每个根节点i下的层数
	public UF4(int n){
		count = n;
		parent=new int[n];
		for(int i=0;i<n;i++){
			parent[i] = i;
			rank[i] = 1; 
 		}
	}
	//让p跟q所在的组的所有数的id都相同
	public void union(int p,int q){
		int pRoot = find(p);
		int qRoot = find(q);
		if(pRoot == qRoot){
			return;
		}
		//parent[pRoot] = qRoot;		
		if(rank[pRoot] < rank[qRoot]){
			parent[pRoot] = qRoot;			
		}else if(rank[pRoot] > rank[qRoot] ){
			parent[qRoot] = pRoot;
		}else{//rank[pRoot] == rank[qRoot]
			parent[pRoot] = qRoot;
			rank[qRoot]++;
		}
	}
	//Quick find 时间复杂度：O(n)
	public int find(int p){
		/*while(parent[p] != p){
			parent[p] = parent[parent[p]];
			p = parent[p];
		}
		return p;*/
		/*第二个版本的路径压缩，通过递归实现*/
		if(parent[p] != p){
			parent[p] = find(parent[p]);//这个方法的返回值是根节点（parent[p] == p）
		}
		return parent[p];
	}
	public boolean isConnected(int p,int q){
		return find(p) == find(q);
	}








}
